package com.lijing.graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

/**
 * @Description TODO
 * @title: Graph
 * @Author LiJing
 * @Date: 2021/3/3112:35 上午
 * @Version 1.0
 */
public class Graph {
    private ArrayList<String> vertexList;
    private int[][] edges;
    private int numOfEdges;
    private boolean[] isVisited;

    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<>(n);
        numOfEdges = 0;
        isVisited = new boolean[5];
    }

    /**
     * 添加节点
     * @param vertex 待添加节点ABCDE
     */
    public void insertVertex(String vertex){
        vertexList.add(vertex);
    }

    /**
     * 无向图
     * @param v1 邻接矩阵顶点下标
     * @param v2 顶点
     * @param weight 权值
     */
    public void insertEdge(int v1, int v2, int weight){
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
    }

    /**
     * 返回顶点数目
     * @return 返回顶点数目
     */
    public int getNumOfVertex(){
        return vertexList.size();
    }

    /**
     * 返回index节点的第一个邻接点
     * @param index 当前节点的
     * @return 存在就返回邻接节点下标，不存在就返回-1
     */
    public int getFirstNeighbor(int index){
        for (int i = 0; i < vertexList.size(); i++) {
            if (edges[index][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * 根据前一个邻接节点的下标来获取下一个邻接节点
     * @param v1 当前节点下标
     * @param v2 当前节点的前一个邻接节点
     * @return 返回后一个邻接节点的下标
     */
    public int getNextNeighbor(int v1, int v2){
        for (int i = v2+1; i < vertexList.size(); i++) {
            if (edges[v1][i] > 0){
                return i;
            }
        }
        return -1;
    }

    /**
     * depth first search
     * @param isVisited 访问情况数组
     * @param i 从第i个节点开始遍历搜索
     */
    public void dfs(boolean[] isVisited, int i){
        /*
         * @Date: 2021/3/31 10:21 下午
         * Step 1: 访问当前节点并打印输出，置为已访问
         */
        System.out.print(getValueByIndex(i)+"->");
        isVisited[i] = true;
        /*
         * @Date: 2021/3/31 10:21 下午
         * Step 2: 查找节点i的第一个邻接节点
         */
        int w = getFirstNeighbor(i);
        /*
         * @Date: 2021/3/31 10:23 下午
         * Step 3: 判断w是否存在，存在，没有访问过就递归w，若访问过w就查找下一个
         * w不存在
         */
        while (w != -1){
            if (!isVisited[w]){
                dfs(isVisited,w);
            }
            w = getNextNeighbor(i,w);
        }
    }

    /**
     * 针对非连通图必须要有这一步
     */
    public void dfs(){
        for (int i = 0; i < getNumOfVertex(); i++) {
            if (!isVisited[i]){
                dfs(isVisited,i);
            }
        }
    }

    public void bfs(boolean[] isVisited, int i){
        int u;
        int w;
        LinkedList queue = new LinkedList();
        System.out.print(getValueByIndex(i)+"->");
        isVisited[i] = true;
        queue.addLast(i);
        while (!queue.isEmpty()){
            u = (Integer) queue.removeFirst();
            w = getFirstNeighbor(u);
            while (w != -1){
                if (!isVisited[w]){
                    System.out.println(getValueByIndex(w)+"->");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u,w);
            }
        }
    }

    public void bfs(){
        for (int i = 0; i < vertexList.size(); i++) {
            if (!isVisited[i]){
                bfs(isVisited,i);
            }
        }
    }

    /**
     * 返回边的数目
     * @return 返回边的数目
     */
    public int getNumOfEdges(){
        return numOfEdges;
    }

    public String getValueByIndex(int i){
        return vertexList.get(i);
    }

    public void showGraph(){
        for (int[] link : edges){
            System.out.println(Arrays.toString(link));
        }
    }



}
